/* tz_linked_list_c.t
 *
 * 27-Nov-2007 Initial write: Ting Zhao
 */

#include <stdlib.h>
#include "tz_error.h"
#include "utilities.h"
#include "tz_double_linked_list.h"

INIT_EXCEPTION

/* Double_List_New(): New a Double list.
 *
 * Return: A Double list with length 1.
 */
Double_List* Double_List_New()
{
  Double_List *new_list = (Double_List *) Guarded_Malloc(sizeof(Double_List), 
						     "Double_List_New");
  new_list->next = NULL;

  return new_list;
}

void Double_List_Set_Data(Double_List *p, double data)
{
  p->data = data;
}

/* Double_List_Removeall(): Remove all nodes in a list.
 *
 * Args: p - a pointer to the list. It becomes NULL after calling this function.
 *
 * Return: void.
 */
void Double_List_Removeall(Double_List **p)
{
  if (p != NULL) {
    while (*p != NULL) {
      Double_List_Remove(p);
    }
  }
}

/* Double_List_Unlinkall(): Unlink all nodes in a list.
 *
 * Args: p - a pointer to the list. It becomes NULL after calling this function.
 *
 * Return: void.
 */
void Double_List_Unlinkall(Double_List **p)
{
  if (p != NULL) {
    while (*p != NULL) {
      Double_List_Unlink(p);
    }
  }
}

void Kill_Double_List(Double_List *p)
{
  Double_List_Removeall(&p);
}

/* Double_List_Add(): Add a node to the beginning of the list.
 * 
 * Args: p - pointer to the list;
 *       data - data node.
 *
 * Return: the old head.
 * 
 * Note: <data> (not its copy) will be added to the list, so be careful about
 *       freeing the object.
 */
Double_List* Double_List_Add(Double_List **p, double data)
{
  Double_List *new_node = Double_List_New();
  new_node->next = *p;
  Double_List_Set_Data(new_node, data);
  *p = new_node;
  
  return (*p)->next;
}

/* Double_List_Add_Last(): Add a new node to the end of the list.
 *
 * Return: the last node of the new list.
 */
Double_List* Double_List_Add_Last(Double_List *p, double data)
{
  p = Double_List_Last(p);
  Double_List *new_node = Double_List_New();
  Double_List_Set_Data(new_node, data);
  p->next = new_node;

  return new_node;
}

/* Double_List_Remove(): Remove the first node.
 *
 * Args: p - a pointer to the list. It becomes the new list after calling this
 *           function.
 *
 * Return: void.
 */
void Double_List_Remove(Double_List **p)
{
  if (*p != NULL) {
    Double_List *tmp_head = *p;
    *p = tmp_head->next;
    
    
    free(tmp_head);
  }
}

void Double_List_Remove_Last(Double_List *p)
{
  if (p == NULL) {
    return;
  }

  while (p->next != NULL) {
    p = Double_List_Next(p);
  }

  Double_List_Remove(&p);
}

/* Double_List_Unlink(): Unlink the head of a list.
 *
 * Args: p - input list, which will be changed.
 *
 * Return: the unlinked data.
 */
double Double_List_Unlink(Double_List **p)
{
  if (*p != NULL) {
    Double_List *tmp_head = *p;
    *p = tmp_head->next;

    double data = tmp_head->data;
    free(tmp_head);
    
    return data;
  }

  
  
  return 0;
  
}

/* Double_List_Next(): Get next node.
 *
 * Return: the next node of p.
 */
Double_List* Double_List_Next(Double_List *p)
{
  return p->next;
}

/* Double_List_Last(): Get the last node.
 *
 * Return: the last node of <p>.
 */
Double_List* Double_List_Last(Double_List *p)
{
  Double_List* prev = NULL;

  while (p != NULL) {
    prev = p;
    p = Double_List_Next(p);
  }

  return prev;
}

BOOL Double_List_Is_Empty(const Double_List *p)
{
  if (p == NULL) {
    return TRUE;
  } else {
    return FALSE;
  }
}

/* Double_List_Length(): Length of the list.
 * 
 * Args: p - input list.
 *
 * Return: the length of the list.
 */
int Double_List_Length(const Double_List *p)
{
  int n = 0;
  while (p != NULL) {
    n++;
    p = p->next;
  }

  return n;
}

/* Double_List_To_Array(): Turn a list to an array.
 *
 * Args: p - input list;
 *       array - returned array. If it is NULL, a new array will be created,
 *               otherwise it must be large enough to hold the result.
 *       step - The offset between an element and its right neighbor. If it is
 *              negative, the array has a reversed order.
 * Return: the resulted array.
 *
 * Note: The caller is responsible for freeing the returned array.
 */
double* Double_List_To_Array(const Double_List *p, int step, double *array, int *length)
{
  if (step == 0) {
    THROW(ERROR_DATA_VALUE);
  }

  int n = Double_List_Length(p);
  int array_length = (n - 1) * abs(step) + 1;

  if (array == NULL) {
    array = (double *) Guarded_Malloc(sizeof(double) * array_length, 
				    "Double_List_To_Array");
  }

  int begin;
  int end;
  
  if (step > 0) {
    begin = 0;
    end = array_length - 1;
  } else {
    begin = array_length - 1;
    end = 0;
  }
  
  int i;
  for (i = begin; p != NULL; i += step, p = p->next) {
    array[i] = p->data;
  }

  if (length != NULL) {
    *length = array_length;
  }

  return array;
}

/* Print_Double_List(): Print Double list.
 *
 * Args: p - list to print.
 *
 * Return: void.
 *
 * Note: This function works only when Print_Double is available.
 */
void Print_Double_List(const Double_List *p)
{
  if (p == NULL) {
    printf("Null list.\n");
    return;
  }

  printf("Total length: %d\n", Double_List_Length(p));

  

}

/* Print_Double_List_Compact(): Print Double list briefly.
 *
 * Args: p - list to print.
 *
 * Return: void.
 *
 * Note: This function works only when Print_Double_Info is available.
 */
void Print_Double_List_Compact(const Double_List *p)
{
  if (p == NULL) {
    printf("Null list.\n");
    return;
  }

  
}

void Print_Double_List_F(const Double_List *p, const char *format)
{
  if (p == NULL) {
    printf("Null list.\n");
    return;
  }

  printf("Total length: %d\n", Double_List_Length(p));
  while (p != NULL) {
    printf(format, p->data);
    printf(" ");
    p = p->next;
  }
  printf("\n");
}

/*
 * The following routines implement a queue based on a list.
 */

/* Double_Queue_En(): Add an item to the end of the queue.
 */
Double_List* Double_Queue_En(Double_List **p, double data)
{
  if (*p == NULL) {
    *p = Double_List_New();
    Double_List_Set_Data(*p, data);
    return *p;
  }

  return Double_List_Add_Last(*p, data);
}

/* Double_Queue_De(): Removes the item from the front of the queue.
 */
double Double_Queue_De(Double_List **p)
{
  return Double_List_Unlink(p);
}

/* Double_Queue_Peek(): Get the iterm from the front of the queue without removing
 *                    it.
 */
double Double_Queue_Peek(const Double_List *p)
{
  return p->data;
}


/*
 * The following routines implement a stack based on a list.
 */
void Double_Stack_Push(Double_List **p, double data)
{
  if (*p == NULL) {
    *p = Double_List_New();
    Double_List_Set_Data(*p, data);
  } else {
    Double_List_Add(p, data);  
  }
}

double Double_Stack_Pop(Double_List **p)
{
  return Double_List_Unlink(p);
}

double Double_Stack_Peek(const Double_List *p)
{
  return p->data;
}


